Digital halftoning is a technique used in image processing to produce a halftone output image from a continuous tone input image. In order to halftone a digital colour image, a continuous tone colour image is sampled, for example with a scanner, and the samples are then digitised and stored in a computer device. In a full colour system, the digitised samples, or pixels, can consist of independent binary representation of the colour components of an image. For example, in the well known red, green and blue system (RGB), utilised in most output displays, the digitised samples or pixels consist of binary representations of the red, green and blue scanned colour values respectively. These binary representations typically range from 0 to 255 for each colour, thereby comprising 8 bits for each primary colour, or 24 bits to represent one pixel. Another colour system involves cyan, magenta, yellow and black (CMYK) and is used predominantly in printer output devices.
Standard cathode ray tube (CRT) type display devices are able to display each pixel with a large number of variations of each colour component of the pixel, giving rise to the desirability of storing 256 possible values for each colour component of each pixel of a CRT type display. Other output devices however, such as printers and certain display devices such as ferro-electric liquid crystal displays are often designed to only be able to display a limited number of colours or intensity values for each output colour. Hence, when displaying an image on such devices, it is necessary to create the sensation of multilevel colours by suitably distributing the possible output colours in the output image. By way of example, it can be assumed that each pixel of a first example display device is able to display red, green and blue colour values (RGB), with each colour value Making either one of a totally on or totally off state. Therefore, each colour component value can display one of two colours and the total number of colours which can be displayed by such a pixel will be 2.times.2.times.2=8 colours.
Two well known methods of halftoning are error diffusion and dithering. To describe error diffusion and dithering, consider by way of example, a monochrome display system where each pixel of an array of pixels can display either black or white. Assume the input image has 256 possible levels of display or values, 0 through 255. A decision must be taken for each pixel whether to display an "off" value of 0 or "on" value of 255.
In error diffusion for this example system, an "off" value is displayed at a current pixel when the input value at the pixel plus error values transferred to the pixel is less than or equal to 127; and an "on" value is displayed when the input value plus error values transferred to the pixel are greater than or equal to 128. An error value at the current pixel is derived, being the input value at the pixel plus the error values transferred to the pixel less the chosen output value. Portions of this error value are then transferred to surrounding pixels which have not, as yet, been output, in accordance with a known distribution mask. This has the effect of spreading, or "diffusing" the error over several pixels in die output image.
It has been found that error diffusion produces unsatisfactory results when an input image comprises video or other forms of data having motion (ie. dynamic images) or noise characteristics. When dynamic images or images having a certain associated noise therein are error diffused, the error diffusion process is subject to slight variations from one frame to the next which in turn results iii pixel values begin turned "on" and "off" at a detectable and distracting rate. This problem can be variously described as "sparkling noise", "dancing dots" and "twinkling", as the effect is to produce an area having rapidly changing individual pixel values but having a substantially constant overall colour. This problem applies equally to both monochrome and full colour display output devices in which such images are displayed.
The halftoning process of dithering traditionally involves the creation of "dither matrix", and the input value of a current pixel is compared with a corresponding value in the dither matrix and an output value for the current pixel is derived. For example, if the dither matrix value is less than the input value of the current pixel, the display device, such as a printer or display, produces an "on" value at the current pixel.
A dither matrix is preferably constructed having certain characteristics which improve the appearance of output halftoned images. These characteristics include arrangement of dither matrix values so that resulting "on" or "off" pixel values are as spread out as possible.
The process of dithering dynamic images, that is, dithering images forming part of an image sequence, however results in the reproduction of images have a noisy "mottled" appearance in regions having a substantially constant colour. Another disadvantage of dithering includes poor edge sharpness at the edges of graphical objects forming part of the image.
While each of the aforementioned halftoning techniques have their own distinct advantages, it is desirable to adopt favourable aspects of each technique.
It is an object of the present invention to provide an alternative form of halftoning which leads to improved output values, at least for various classes of images or image sequences.